// BackTracking.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

/*
* 回溯其实是一种递归, 回溯的过程发生在递归函数调用之后。
* 在递归函数调用结束之后, 就是回溯部分的内容。
* 
* 回溯是一种纯暴力的搜索技巧, 并不是一种高效的算法。
* 回溯是用于解决无法使用暴力迭代搜索出结果的问题。
* 
* 一般用于解决以下问题:
*   1.组合: 给出集合, 求出对应条件的组合
*   2.切割: 例如字符串切割
*   3.子集: 获取集合包含的子集
*   4.排列: 获取集合的排列集合
*   5.棋盘: N皇后、解数独
*  
* 可以将回溯理解为一个树结构:
*   1.树的宽度代表集合的大小, 可以理解为每个节点处理的集合的大小(使用 for 循环)
*   2.树的深度代表递归的深度
*   3.
* 
* 递归函数模板:
*   void BackTracking(params ...) {
*       //终止条件, 搜集结果 (叶子节点)
*       if (condition) {
*           do sth... (collect results)
*           return;
*       }
*       
*       //单层搜索逻辑
*       for (集合元素) {
*           //处理节点, 将处理结果作为新的节点放入递归函数
*           //递归函数
*           //回溯操作, 回溯节点
*       }
*   }
* 
*   三部曲:
*     1.递归函数参数
*     2.终止条件
*     3.单层递归逻辑
*/

#include <iostream>
#include "Composite.h"
#include "Clipping.h"
#include "SubSet.h"
#include "LIS.h"
#include "Permutation.h"
#include "NQueens.h"
#include "Sudoku.h"

int main()
{
    vector<int> n = { 1, 2, 3, 4 };
    int k = 2;

    vector<int> path;
    vector<vector<int>> results;
    //BackTracking(n, k, path, results);

    BackTrackingWithClip(n, k, path, results);

    vector<int> n1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    vector<int> path1;
    vector<vector<int>> results1;
    BackTrackingAccumulateI(n1, path1, results1, 9, 3);

    vector<int> pathII;
    vector<vector<int>> resultsII;
    BackTrackingAccumulateII(n1, 4, pathII, resultsII);

    vector<int> nIII = { 10, 1, 2, 7, 6, 1, 5 };
    sort(nIII.begin(), nIII.end());
    vector<int> pathIII;
    vector<vector<int>> resultsIII;
    vector<bool> bUsed(n1.size(), false);
    BackTrackingAccumulateIII(nIII, 8, pathIII, bUsed, resultsIII);

    vector<int> digits = { 2, 3 };
    string path2;
    vector<string> result2;
    BackTrackingLetter(digits, path2, result2);

    string str = "abcd";
    vector<string> pathClipping;
    vector<vector<string>> resultClipping;

    BackingTrackingClipping(str, pathClipping, resultClipping);

    string str1 = "aab";
    vector<string> pathPalindrome;
    vector<vector<string>> resultPalindrome;
    BackingTrackingPalindrome(str1, pathPalindrome, resultPalindrome);

    string ipAddress = "101023";
    vector<string> pathIpAddress;
    vector<vector<string>> resultIpAddress;
    BackTrackingIpAddress(ipAddress, pathIpAddress, resultIpAddress);

    vector<string> resultIpAddress1;
    BackTrackingIpAddress(ipAddress, resultIpAddress1);

    vector<int> set = {1, 2, 3};
    vector<int> pathSubSets;
    vector<vector<int>> resultsSubSets;
    BackTrackingSubSets(set, pathSubSets, resultsSubSets);

    vector<int> setII = { 1, 2, 2 };
    sort(setII.begin(), setII.end());
    vector<int> pathSubSetsII;
    vector<vector<int>> resultsSubSetsII;
    vector<bool> bUsedII(setII.size(), false);
    BackTrackingSubSetsII(setII, pathSubSetsII, resultsSubSetsII, bUsedII);

    vector<int> LIS = { 4, 7, 6, 7 };
    vector<int> pathLIS;
    vector<vector<int>> resultsLIS;
    BackTrackingLIS(LIS, pathLIS, resultsLIS);

    vector<int> pathPermutation;
    vector<vector<int>> resultsPermutation;
    vector<bool> bUsedPermutation(set.size(), false);
    BackTrackingPermutation(set, pathPermutation, resultsPermutation, bUsedPermutation);

    vector<int> pathPermutationII;
    vector<vector<int>> resultsPermutationII;
    vector<bool> bUsedPermutationII(setII.size(), false);
    BackTrackingPermutationII(setII, pathPermutationII, resultsPermutationII, bUsedPermutationII);

    vector<string> chessboard(4, "....");
    vector<vector<string>> resultsNQueen;
    BackTrackingNQueens(chessboard, resultsNQueen);

    vector<vector<char>> sudoku = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };

    bool result = BackTrackingSudoku(sudoku);

    vector<vector<char>> sudokuII = {
    {'.','.','.','.','.','.','6','.','.'},
    {'.','.','.','.','.','.','.','.','3'},
    {'2','4','.','.','.','.','.','.','.'},
    {'.','7','8','.','.','.','.','.','.'},
    {'.','.','.','6','.','.','8','.','.'},
    {'.','.','1','4','.','.','.','7','.'},
    {'.','.','.','3','.','.','9','.','.'},
    {'5','.','7','.','.','8','.','4','.'},
    {'.','.','6','5','.','4','3','.','1'}
    };
    vector<vector<vector<char>>> resultII;

    BackTrackingSudokuII(sudokuII, resultII);
}
